# 花越开越多，T天如果可行（能制作），T+1,T+2,...天都可行（能制作）- 单调分段
# 判定：mid天的开花情况，能否制作m束花，每束花是连续的k朵

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        latestBloom = 0
        for bloom in bloomDay:
            latestBloom = max(latestBloom, bloom)
        left = 0
        right = latestBloom + 1
        while left < right:
            mid = (left + right) >> 1
            if self.validateOnDay(bloomDay, m, k, mid):
                right = mid
            else:
                left = mid + 1
        if right == latestBloom + 1:
            return -1
        return right

    # 判定：第T天的开花情况，能否制作m束花，每束花是连续的k朵
    def validateOnDay(self, bloomDay, m, k, now):
        bouquet = 0
        consecutive = 0
        for bloom in bloomDay:
            if bloom <= now:
                consecutive += 1
                if consecutive == k:
                    bouquet += 1
                    consecutive = 0
            else:
                consecutive = 0
        return bouquet >= m